﻿//输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
//例如输入字符串ABC, 则输出由字符A, B, C所能排列出来的所有字符串ABC, ACB, BAC, BCA, CBA和CAB。
//
//数据范围：n < 10
//要求：空间复杂度O(n!)，时间复杂度O(n!)
//
//输入描述：
//	输入一个字符串, 长度不超过10, 字符只包括大小写字母。
//
//输入：
//	"ab"
//返回值：
//	["ab", "ba"]
//说明：
//	返回["ba", "ab"]也是正确的
//
//输入：
//	"aab"
//返回值：
//	["aab", "aba", "baa"]
//
//输入：
//	"abc"
//返回值：
//	["abc", "acb", "bac", "bca", "cab", "cba"]
//
//输入：
//	""
//返回值：
//	[""]

class Solution {
public:
    vector<string> ret; // 收集叶⼦结点
    string path; // 记录路径的信息
    bool vis[11] = { 0 }; // 标记当前位置时候已经使⽤过
    int n;
    string s;
    vector<string> Permutation(string str) {
        n = str.size();
        sort(str.begin(), str.end());
        s = str;

        dfs(0);
        return ret;
    }
    void dfs(int pos) {
        if (pos == n) {
            ret.push_back(path);
            return;
        }
        // 填 pos 位置
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                if (i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;
                path.push_back(s[i]);
                vis[i] = true;
                dfs(pos + 1);
                // 恢复现场
                vis[i] = false;
                path.pop_back();
            }
        }
    }
};







